A Hybrid Adjacency and Time-Based Data Structure for Analysis of Temporal Networks
- Project Research
- 1-5 Chapters
- Abstract : Available
- Table of Content: Available
- Reference Style: APA
- Recommended for : Student Researchers
- NGN 3000
Background
Related Work I begin with background information on ways for representing temporal networks and data structures for storing (static) networks. I then discuss work related to this thesis, including the use of hybrid data structures and other types of temporal network data structures. 2.1 Static Network Representations Static networks are typically represented in one of 3 ways [41]: • Adjacency matrix : A two-dimensional matrix, Auv, stores edge information for source node u to destination node v in the uvth element of the matrix. • Adjacency list: A set of lists, one for each source node u. Each list contains a series of destination nodes v, if edge (u, v) exists. • Adjacency dictionary: A hash table keyed by source nodes u mapped to the set of destination nodes v, if edge (u, v) exists. The adjacency matrix is the traditional data structure for network representation due to, in part, its simple construction, but also its prominence in key aspects of network analysis, such as spectral graph theory. The values stored in adjacency 7 matrices are typically boolean in nature, with a value of ”1” representing an edge is present between two nodes, and a value of ”0” otherwise. However, adjacency matrices can be modified to hold additional information by storing numeric values instead, e.g. edge weights. Since an adjacency matrix stores a value for both present and missing edges, it has a memory complexity of O(n 2 ), where n is the number of nodes, and is therefore only appropriate for smaller networks. The adjacency list representation aims to improve upon this memory complexity by removing the need to store missing edge information. By storing edges as a set of list, adjacency lists improve the memory complexity to O(k), where k is the number of edges. However, this approach suffers from increased time complexity during common operations such as finding if an edge exists between nodes u and v due to the unsorted nature of its lists. The adjacency dictionary representation is a variant on the standard adjacency list, by storing the edges in a hashed set rather than a list. Edges presence in an adjacency dictionary can be determined in O(1) time, matching the adjacency matrix, while retaining the O(k) space complexity of the adjacency list. By using a hash table instead of a hashed set, additional edge information can be stored inside the adjacency dictionary as well.
Related Project Materials
POSSIBLE EFFECTS OF ELECTROMAGNETIC FIELDS (EMF) ON HUMAN HEALTH
ABSTRACT
This work on ”Possible effects of Electromagnetic Fields (EMF), Radio Frequency Fields (RF) and Microwave...
THE EFFECT OF CLASS SIZE AND OVER POPOLATION ON THE ACADEMIC PERFORMANCE OF SECONDARY SCHOOL STUDENTS
ABSTRACT
This research was performed to examine the influence of class room size on academic performance of secondary sc...
IMPACT OF SERVICE QUALITY ON CUSTOMER RETENTION IN THE NIGERIAN BANKING SECTOR
ABSTRACT
The study examined the impact of service quality on customer retention in the Nigerian banking sector. Staff of...
THE IMPACT OF ADVERTISING ON THE DEVELOPMENT OF THE MEDIA
BACKGROUND OF THE STUDY
Advertising has been defined as “a powerful communication force and a vital marketing tool...
STUDY OF THE IMPACT OF UNIVERSAL BANKING IN NIGERIA FINANCIAL SYSTEM
ABSTRACT
The study of the impact of universal Banking is one of the critical for banks Nigeria to attain greater light....
EFFECT OF PARENTS INTERVENTION ON PERFORMANCE OF STUDENTS IN COLLEGE ENTRANCE EXAMINATION
Background To The Study
Parental participation has a significant impact on children's academic perf...
THE EFFECT OF EDUCATION ANXIETY ON THE ACADEMIC PERFORMANCE OF STUDENTS IN TERTIARY INSTITUTIONS
ABSTRACT
This project titled the effect of education anxiety on the academic performance of students in tertiary institu...
THE IMPACT OF MONETARY POLICY ON INDUSTRIAL GROWTH IN NIGERIA
ABSTRACT
This study empirically examines the Impact of Monetary Policy on Industrial Growth in Nigerian...
IMMORALITY IN CHURCHES: ISSUES AND THE WAY FORWARD
Abstracts
The study examines immorality in churches: issues and the way forward. Specifically, the study aims to examine...
IMPACT OF TOP RANK HOTELS PROFITABILITY THROUGH ADVERTISING IN N.T.A. ENUGU.
Background of the Study
The impact of advertising for businesses and brands in the 21st century has become imperatively permanent and the...
